package org.eoti.math.brocot;

import org.eoti.math.Fraction;
import org.eoti.math.cf.SimpleCF;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.ArrayList;
import java.util.concurrent.LinkedBlockingDeque;

public class SternBrocot
{
    public enum Choice{Up,Left,Right}
    private LinkedBlockingDeque<Node> path;
    private Node defaultNode;

    public SternBrocot()
    {
        path = new LinkedBlockingDeque<Node>();
        defaultNode = new Node(
            new Fraction(
                BigInteger.ZERO,
                BigInteger.ONE
            ),
            new Fraction(
                BigInteger.ONE,
                BigInteger.ZERO
            )
        );
        path.add(defaultNode);
    }

    public void move(Choice direction)
    {
        Node last = path.peekLast();
        switch(direction)
        {
            case Up:
                path.pollLast();
                if(path.isEmpty())
                    path.add(defaultNode);
                break;
            case Left:
                path.addLast(new Node(last.low, last.middle));
                break;
            case Right:
                path.addLast(new Node(last.middle, last.high));
                break;
        }
    }

    public SimpleCF toCF()
    {
        return new SimpleCF(getCF());
    }

    public static SternBrocot findCF(String target, boolean incrementalOutput)
    {
        SternBrocot brocot = new SternBrocot();
        boolean isLeft = true;
        boolean started = false;
        for(String part : target.split("[\\[\\]\\,\\;\\.]+"))
        {
            part = part.trim();
            if(part.length() == 0) continue;
            Integer value = Integer.parseInt(part);
            if(!started && value == 0)
            {
                // less than 1; we'll switch to left on the next number
                isLeft = false;
            }else{
                isLeft = !isLeft;
                for(int i=0; i<value; i++)
                {
                    if(isLeft) brocot.move(Choice.Left);
                    else brocot.move(Choice.Right);
                }
            }
            started = true;
            if(incrementalOutput) System.out.format("%s\n", brocot.toString());
        }
        // CF has 1 extra at the end
        brocot.move(Choice.Up);
        if(incrementalOutput) System.out.format("%s\n", brocot.toString());
        return brocot;
    }

    public static SternBrocot find(String target, boolean incrementalOutput)
    {
        SternBrocot brocot = new SternBrocot();
        for(int i=0; i<target.length(); i++)
        {
            char c = target.charAt(i);
            if(c == 'L')
                brocot.move(Choice.Left);
            else if(c == 'R')
                brocot.move(Choice.Right);

            if(incrementalOutput) System.out.format("%s\n", brocot.toString());
        }
        return brocot;
    }

    public static SternBrocot find(BigDecimal target, boolean incrementalOutput)
    {
        SternBrocot brocot = new SternBrocot();
        boolean done = false;
        while(!done)
        {
            BigDecimal current = brocot.getFraction().compute(MathContext.DECIMAL128);
            int comparison = current.compareTo(target);
            if(comparison < 0) // current < target
                brocot.move(Choice.Right);
            else if(comparison > 0)
                brocot.move(Choice.Left);
            else
                done = true;

            if(incrementalOutput) System.out.format("%s\n", brocot.toString());
        }
        return brocot;
    }

    public static SternBrocot find(Fraction target, boolean incrementalOutput)
    {
        SternBrocot brocot = new SternBrocot();
        boolean done = false;
        while(!done)
        {
            int comparison = brocot.getFraction().compareTo(target);
            if(comparison < 0) // current < target
                brocot.move(Choice.Right);
            else if(comparison > 0)
                brocot.move(Choice.Left);
            else
                done = true;

            if(incrementalOutput) System.out.format("%s\n", brocot.toString());
        }
        return brocot;
    }

    public String getPath()
    {
        StringBuilder builder = new StringBuilder();
        Node last = null;
        for(Node node : path)
        {
            if(last != null)
            {
                int comparison = last.compareTo(node);
                if(comparison < 0) builder.append("R");
                else if(comparison > 0) builder.append("L");
                else builder.append("-");
            }
            last = node;
        }
        return builder.toString();
    }

    public Fraction getFraction()
    {
        Node node = path.peekLast();
        return node.middle;
    }

    public String toString()
    {
        Fraction fraction = getFraction();
        String thePath = getPath();
        String decimal = fraction.compute(MathContext.DECIMAL128).stripTrailingZeros().toPlainString();
        return String.format("[SternBrocot: [%s] [%s] [%s] %s]", fraction, decimal, thePath, getCF());
    }

    public String getCF()
    {
        String tree = getPath();
        ArrayList<Integer> list = new ArrayList<Integer>();
        boolean isLeft = false;
        char current='A';
        int count = 0;
        for(int i=0; i<tree.length(); i++)
        {
            char c = tree.charAt(i);
            if(i == 0)
            {
                // if it starts with 'L' then it is less than 1; CF needs leading 0
                isLeft = (c == 'L');
                if(isLeft)
                    list.add(0);

                current = c;
                count++;
            }else if(c != current){
                list.add(count);
                isLeft = !isLeft;
                current = c;
                count = 1;
            }else{
                current = c;
                count++;
            }
        }
        list.add(count+1);

		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for(int i=0; i<list.size(); i++)
		{
			if(i == 0){/* no-op */}
			else if(i==1) sb.append(";");
			else sb.append(",");
			sb.append(""+list.get(i));
		}
		sb.append("]");
		return sb.toString();
    }

    public void reset()
    {
        path.clear();
        path.add(defaultNode);
    }

    static class Node implements Comparable<Node>
    {
        protected Fraction low,high,middle;
        public Node(Fraction low, Fraction high)
        {
            this.low = low;
            this.high = high;
            this.middle = new Fraction(
                low.getNumerator().add(high.getNumerator()),
                low.getDenominator().add(high.getDenominator())
            );
        }
        public String toString(){return middle.toString();}

        @Override
        public int compareTo(Node node) {
            return middle.compareTo(node.middle);
        }
    }

    public static void main(String ... args)
    {
        if(args.length == 0)
        {
            System.err.format("USAGE: java org.eoti.math.brocot.SternBrocot [-i] {target}\n");
            System.err.format("WHERE '-i' will print out incremental results\n");
            System.err.format("AND 'target' is in one of these forms:\n");
            System.err.format("\tRRRLLLLLLLRRRRRRRRRRRRRRRLRRRRRRRRRRRRRRRRRRRRRRRRRLRRRRRRRLLL\n");
            System.err.format("\t3.14159\n");
            System.err.format("\t314159/100000\n");
            System.err.format("\t[3;7,15,1,25,1,7,4]\n");
            System.exit(1);
        }

        SternBrocot brocot = null;
        boolean incrementalOutput = (args.length == 2 && args[0].equals("-i"));
        String toTest = ((args.length == 2) ? args[1] : args[0]).trim();
        for(int i=0; i<toTest.length(); i++)
        {
            char c = toTest.charAt(i);
            if(c == 'R' || c == 'L')
            {
                brocot = SternBrocot.find(toTest, incrementalOutput);
                break;
            }
            if(c == '/')
            {
                brocot = SternBrocot.find(new Fraction(new BigInteger(toTest.substring(0,i)), new BigInteger(toTest.substring(i+1))), incrementalOutput);
                break;
            }
            if(c == '[' || c == ';' || c== ',' || c == ']')
            {
                brocot = SternBrocot.findCF(toTest, incrementalOutput);
                break;
            }
        }
        if(brocot == null)
            brocot = SternBrocot.find(new BigDecimal(toTest), incrementalOutput);

        System.out.format("RESULT: %s\n", brocot);
    }
}
